class Solution170 {
    public static void main(String[] args) {
        int[] arr = {7,5,6,4} ;
        System.out.println(reversePairs(arr));
    }
    static int[] tmp ;
    public static int reversePairs(int[] record) {
       tmp = new int[record.length] ; 
       return mergeSort(record , 0 , record.length-1) ; 
    }
    private static int mergeSort(int[] nums , int left , int right){
        if(left >= right) return 0 ; 
         int mid = left + (right-left)/2 ;
         int sum = mergeSort(nums , left , mid) + mergeSort(nums ,mid+1 , right) ; 
         int i = 0 , l = left , r = mid+1 ;
         while(l <= mid && r <= right){
             if(nums[l] <= nums[r]){
               tmp[i++] = nums[l++] ; 
             }else{
               sum += mid-l+1 ;
               tmp[i++] = nums[r++] ; 
             }
         }
         while(l <= mid){
            tmp[i++] = nums[l++] ; 
         }
         while(r <= right){
            tmp[i++] = nums[r++] ; 
         }
        for(int j=left ; j <= right ; j ++){
            nums[j] = tmp[j-left];
        }
        return sum ;
    }
    
}